package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname InsertSort
 * @Project Data-structure-and-algorithm
 * @Description 插入排序代码实现
 * 插入排序(Insertion Sorting）的基本思想是:
 * 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，也就是数组第一个数，无
 * 序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它依次与有序表元素从后往前进行比较，记录下标，
 * 等找到适合插入的位置下标，就将它插入到有序表中的适当位置，使之成为新的有序表。
 * @Author wpcheng
 * @Create 2021-08-05-8:48
 * @Version 1.0
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {34,23,12,25};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
    }

    public static void insertSort(int[] arr){

        int insertValue = arr[1]; //把数组第二个数取出，存入 insertValue
        int insertIndex = 0; //第一个数的下标，insertValue参照insertIndex进行有序插入

        //insertIndex >=0 保证数组下标不会越界，从insertIndex开始，往前索引，相当于insertValue往前一个个的进行比较
        //insertValue < arr[insertIndex] 当前数 insertValue 小于前面的数
        while (insertIndex >=0 && insertValue < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex]; //后移，把位置让出来
            insertIndex--; //下标前移
        }
        //当退出while循环时，说明已经找到了插入位置
        arr[insertIndex + 1] = insertValue;
        System.out.println("第一轮排序：");
        System.out.println(Arrays.toString(arr));


        insertValue = arr[2]; //把数组第三个数取出，存入 insertValue
        insertIndex = 1; //第二个数的下标

        //insertIndex >=0 保证数组下标不会越界
        //insertValue < arr[insertIndex] 当前数 insertValue 小于前面的数
        while (insertIndex >=0 && insertValue < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex]; //后移，把位置让出来
            insertIndex--; //下标前移
        }
            arr[insertIndex + 1] = insertValue;


        System.out.println("第二轮排序：");
        System.out.println(Arrays.toString(arr));

        insertValue = arr[3]; //把数组第四个数取出，存入 insertValue
        insertIndex = 2; //第三个数的下标

        //insertIndex >=0 保证数组下标不会越界
        //insertValue < arr[insertIndex] 当前数 insertValue 小于前面的数
        while (insertIndex >=0 && insertValue < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex]; //后移，把位置让出来
            insertIndex--; //下标前移
        }
        arr[insertIndex + 1] = insertValue;
        System.out.println("第三轮排序：");
        System.out.println(Arrays.toString(arr));



    }
}
